package acm.pta3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class T14 {

    public static void main(String[] args) throws IOException {
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        Graph graph=new Graph();
        String[] read = null;
        read=in.readLine().split(" ");
        int n=Integer.parseInt(read[0])-1;
        int m=Integer.parseInt(read[1]);
        Node start = new Node(read[2],0);
        String endStr=read[3];
        graph.add(start);
//        graph.add(end);
        while (n-- > 0) {
            read=in.readLine().split(" ");
            graph.add(new Node(read[0],Integer.parseInt(read[1])));
        }
        while (m-- > 0) {
            read=in.readLine().split(" ");
            graph.add(read);
        }
        Node end = graph.nodes.get(endStr);
        fun(start,end,graph.nodes.size());
    }
    /**
     * 最短路径方案数
     */
    public static void fun(Node start,Node end,int size){
        NodeHeap heap=new NodeHeap(size);
        heap.addOrUpdateOrIgnore(null,start,0,0,0);
        NodeHeap.NodeRecord record=null;
        while (heap.isNotEmpty()) {
            record = heap.pop();
            Node curr = record.node;
            if (curr==end){
                break;
            }
            for (Edge edge : curr.edges) {
                heap.addOrUpdateOrIgnore(
                        curr,
                        edge.to,
                        record.distance+edge.weight,
                        record.pass+1,
                        record.kill+edge.to.val);
            }
        }
        printPass(heap.preMap,end);
        System.out.println(builder.substring(0,builder.length()-2));
        System.out.printf("%d %d %d");
    }
    static StringBuilder builder=new StringBuilder();
    public static void printPass(Map<Node,Node> map,Node curr){
        if (curr==null){
            return;
        }
        printPass(map,map.get(curr));
        builder.append(curr.name).append("->");
    }
    static class Graph{
        Map<String,Node> nodes=new HashMap<>();

        public void add(Node node){
            nodes.put(node.name,node);
        }
        public void add(String[] edgeStr){
            Node from = nodes.get(edgeStr[0]);
            Node to = nodes.get(edgeStr[1]);
            Edge toTO = new Edge(from,to,Integer.parseInt(edgeStr[2]));
            Edge toFrom = new Edge(to,from,toTO.weight);
            from.edges.add(toTO);
            to.edges.add(toFrom);
        }
    }
    static class Node{
        String name;
        int val;
        List<Edge> edges=new ArrayList<>();

        public Node(String name, int val) {
            this.name = name;
            this.val = val;
        }
    }
    static class Edge{
        Node from;
        Node to;
        int weight;

        public Edge(Node a, Node b, int weight) {
            this.from = a;
            this.to = b;
            this.weight = weight;
        }
    }
    static class NodeHeap{
        Node[] nodes;
        Map<Node,Integer> indexMap;     //节点在堆中的位置
        int heapSize;
        Map<Node,Node>preMap;
        Map<Node,Integer>distanceMap;
        Map<Node,Integer>passMap;
        Map<Node,Integer>killMap;


        public NodeHeap(int size) {
            this.nodes=new Node[size];
            indexMap=new HashMap<>(size);
            distanceMap=new HashMap<>(size);
            passMap=new HashMap<>(size);
            killMap=new HashMap<>(size);
            preMap=new HashMap<>(size);
        }

        /**
         * 返回true，o1在前面，返回false，o2在前
         */
        public boolean compare(Node o1,Node o2){
            Integer dist1 = distanceMap.get(o1);
            Integer dist2 = distanceMap.get(o2);
            if (dist1 == dist2){
                Integer pass1 = passMap.get(o1);
                Integer pass2 = passMap.get(o2);
                if (pass1==pass2){
                    return killMap.get(o1)>=killMap.get(o2);
                }
                return pass1>pass2;
            }
            return dist1 < dist2;
        }
        public boolean compare(Node o1,int dist2,int pass2,int kill2){
            Integer dist1 = distanceMap.get(o1);
            if (dist1 == dist2){
                Integer pass1 = passMap.get(o1);
                if (pass1==pass2){
                    return killMap.get(o1)>=kill2;
                }
                return pass1>pass2;
            }
            return dist1 < dist2;
        }
        /**
         * 如果节点不存在则添加
         * 节点存在且比原来要近则更新，更远则不更新
         */
        public void addOrUpdateOrIgnore(Node from,Node to,int distance,int pass,int kill){
            if (from==null){
                heapInsert(to,heapSize++,distance,pass,kill);
                return;
            }
            if (!distanceMap.containsKey(to)){
                heapInsert(to,heapSize++,distance,pass,kill);
                preMap.put(from,to);
                return;
            }
            if (!compare(to,distance,pass,kill)){
                heapInsert(to,heapSize++,distance,pass,kill);
                preMap.put(from,to);
                heapify(indexMap.get(to));
            }
        }

        /**
         * 从指定位置插入节点
         * 需要哪些信息？
         * 1.节点
         * 2.所在位置
         */
        public void heapInsert(Node o,int i,int distance,int pass,int kill){
            distanceMap.put(o,distance);
            passMap.put(o,pass);
            killMap.put(o,kill);
            Node parentNode=nodes[(i-1)/2];
            while (compare(o,parentNode)){
                swap(i,(i-1)/2);
                i=(i-1)/2;
                parentNode=nodes[i];
            }
        }
        /**
         * 从指定位置移除节点
         */
        public void heapify(int i){
            int left=i*2+1;
            while (left<heapSize){
                int minIndex = left+1<heapSize&&compare(nodes[left+1],nodes[left]) ?
                        left+1: left;
                if (compare(nodes[i],nodes[minIndex])) {   //当前节点仍是最近节点
                    return;
                }
                swap(minIndex,i);
                i=minIndex;
                left=i*2+1;
            }
        }
        public NodeRecord pop(){
            return null;
        }
        public boolean isNotEmpty(){
            return heapSize>0;
        }

        public void swap(int a,int b){
            Node node=nodes[a];
            nodes[a]=nodes[b];
            nodes[b]=node;
            indexMap.put(nodes[a],a);
            indexMap.put(nodes[b],b);
        }

        static class NodeRecord{
            Node node;
            int distance;
            int pass;
            int kill;

            public NodeRecord(Node node, int distance, int pass, int kill) {
                this.node = node;
                this.distance = distance;
                this.pass = pass;
                this.kill = kill;
            }
        }
    }
}
